package com.jxb.three;

/**
 * 下一个排列
 * 输入：nums = [1,2,3]
 * 1，2，3
 * 1，3，2
 * 2，1，3
 * 2，3，1
 * 3，1，2
 * 3，2，1
 * 输出：[1,3,2]
 *
 * 思路：
 *  1：循环找出数组中的小数（nums[i] < nums[i+1]）
 *  2：找出数组中尽可能的大数，与小数进行交换(nums[i]<nums[j])
 *  3：对大数后面的所有数进行升序
 */
public class NextPermutation_31 {

    public static void main(String[] args) {

    }

    public void nextPermutation(int[] nums) {
        int i = nums.length - 2;
        //找到数组中的“小数”，进行循环找出nums[i]<nums[i+1]
        while (i>=0 && nums[i] >= nums[i+1]) {
            i--;
        }
        //找到数组中尽可能小的大数，与小数替换
        if (i>0) {
            int j = nums.length - 1;
            while (j >= 0 && nums[i] > nums[j]) {
                j--;
            }
            //交换小数与大数
            swap(nums, i, j);
        }
        //将大数后面的所有数重置为升序
        reverse(nums, i + 1);
    }

    private void reverse(int[] nums, int start) {
        int left = start;
        int right = nums.length - 1;
        while (left < right) {
            swap(nums,left,right);
            left++;
            right--;
        }
    }

    public void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }

}
